package com.zac.coroutine.algorithm.leetcode.tree;

import java.util.LinkedList;

/**
 * author zac
 * date 2024/11/21
 * 110. 平衡二叉树
 * 简单
 * 给定一个二叉树，判断它是否是
 * 平衡二叉树
 */
public class TreeTest4 {

    // [1,2,3,4,5,6,null,8]

    /**
     *
     * 1
     * 2             3
     * 4    5        6
     * 8
     * @param root
     * @return
     */

    public boolean isBalanced(TreeNode root) {
        LinkedList<Integer> list = new LinkedList<>();
        LinkedList<Integer> list1 = recordDepth(root, 0, list);

        int min = -1, max = -1;
        for (Integer i : list1) {
            if (min == -1 || i < min) {
                min = i;
            }
            if (max == -1 || i > max) {
                max = i;
            }
            if (max - min >= 2) {
                return false;
            }
        }

        return true;

    }

    public LinkedList<Integer> recordDepth(TreeNode node, int depth, LinkedList<Integer> list) {
        if (node == null) {
            list.add(depth);
        } else {
            recordDepth(node.left, depth + 1, list);
            recordDepth(node.right, depth + 1, list);
        }
        return list;
    }


}
